package problem120_Triangle;

import java.util.List;

/**
 * dp[i][j]代表第i行第j个点到达底部所需的最小path sum。
 * dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
 * 
 * @author Ivan
 *
 */
public class Solution {
	public int minimumTotal(List<List<Integer>> triangle) {
		int[][] dp=new int[triangle.size()][triangle.get(triangle.size()-1).size()];
		for(int i=0;i<dp[dp.length-1].length;i++){
			dp[dp.length-1][i]=triangle.get(dp.length-1).get(i);
		}
        for(int i=triangle.size()-2;i>=0;i--){
        	for(int j=0;j<triangle.get(i).size();j++){
        		dp[i][j]=Math.min(dp[i+1][j], dp[i+1][j+1])+triangle.get(i).get(j);
        	}
        }
        return dp[0][0];
    }
	
	public int minimumTotal2(List<List<Integer>> triangle) {
		int m=triangle.size();
		int[] dp=new int[m];
		for(int i=0;i<m;i++){
			dp[i]=triangle.get(m-1).get(i);
		}
		for(int i=m-2;i>=0;i--){
			for(int j=0;j<=i;j++){
				dp[j]=Math.min(dp[j], dp[j+1])+triangle.get(i).get(j);
			}
		}
		return dp[0];
    }
}
